|
In computer science, double pushout graph rewriting or (DPO graph rewriting) refers to a mathematical framework for graph rewriting. It was introduced as one of the first algebraic approaches to graph rewriting in the article "Graph-grammars: An algebraic approach" (1973).〔"Graph-grammars: An algebraic approach", Ehrig, Hartmut and Pfender, Michael and Schneider, Hans-Jürgen, Switching and Automata Theory, 1973. SWAT'08. IEEE Conference Record of 14th Annual Symposium on, pp. 167-180, 1973, IEEE〕 It has since been generalized to allow rewriting structures which are not graphs, and to handle negative application conditions,〔"Constraints and application conditions: From graphs to high-level structures", Ehrig, Ehrig, Habel and Pennemann, Graph transformations, pp. 287--303, Springer〕 among other extensions. == Definition == A DPO graph transformation system (or graph grammar) consists of a finite graph, which is the starting state, and a finite or countable set of labeled spans in the category of finite graphs and graph homomorphisms, which serve as derivation rules. The rule spans are generally taken to be composed of monomorphisms, but the details can vary.〔"Double-pushout graph transformation revisited", Habel, Annegret and Müller, Jürgen and Plump, Detlef, Mathematical Structures in Computer Science, vol. 11, no. 05., pp. 637--688, 2001, Cambridge University Press〕 Rewriting is performed in two steps: deletion and addition. After a match from the left hand side to is fixed, nodes and edges that are not in the right hand side are deleted. The right hand side is then glued in. Gluing graphs is in fact a pushout construction in the category of graphs, and the deletion is the same as finding a pushout complement, hence the name. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Double pushout graph rewriting」の詳細全文を読む スポンサード リンク
|